#pragma once
#include<vector>
using namespace std;

class UnionFind
{
public:

	UnionFind(int _n,vector<int> _prev,vector<int> _rank)
		:n(_n)
		,prev(_prev)
		,rank(_rank)
	{
		for (int i = 1; i <= n; i++)
		{
			prev[i] = i;
			rank[i] = 1;
		}
	}

	int find(int x)
	{
		if (prev[x] == x)
		{
			return x;
		}

		return prev[x] = find(prev[x]);
	}

	bool isSame(int x, int y)
	{
		return find(x) == find(y);
	}

	bool Union(int x, int y)
	{
		x = find(x);
		y = find(y);

		if (x == y)
		{
			return false;
		}

		if (rank[x] > rank[y])
		{
			prev[y] = x;
		}
		else 
		{
			if (rank[x] == rank[y])
			{
				rank[y]++;
			}

			prev[x] = y;
		}

		return true;
	}

private:
	int n;
	vector<int> prev;
	vector<int> rank;
};

